package interview.heap;

/**
 * Created by yzy on 2021-01-26 10:19
 */
public class TopKSolution {

    public static void main(String[] args) {

    }

    public static int topK(int[] arr, int k){
        int[] minTopHeap = createMinTopHeap(arr, k);
        for(int i=k; i<arr.length; i++){
            if(arr[k] > minTopHeap[0]){
                insertToHeap(minTopHeap, arr[k]);
            }
        }
        return minTopHeap[0];
    }

    /**
     * 创建小顶堆
     * 1、创建大小为k的数组当做堆
     * 2、从开始，循环k次，依次入堆
     * 3、入堆前，认为当前为子节点，向上找父节点，并且比较大小。循环条件（小顶堆）：parentIdx>0 && heap[parentIdx] > val
     * 4、如果子节点小于父节点的Val，那么节点上浮一次，交换上一个节点数据为当前idx赋值，childIdx变为上一个父节点Idx，继续下一轮循环
     * 6、循环结束后，由于上一步childIdx=parentIdxOld，所以此时的空位是childIdx，直接赋值当前arr[i]的值即可
     * @param arr
     * @param k
     * @return
     */
    private static int[] createMinTopHeap(int[] arr, int k){
        int[] heap = new int[k];
        for(int i=0; i<k; i++){
            int val = arr[i];
            int childIdx = i;
            int parentIdx = (childIdx-1)/2;
            while(parentIdx >0 && heap[parentIdx] > val){
                heap[childIdx] = heap[parentIdx];
                childIdx = parentIdx;
                parentIdx = (childIdx - 1) /2;
            }
            heap[childIdx] = val;
        }
        return heap;
    }


    /**
     * 1、先把顶部值替换
     * 2、parentIdx = 0
     * 3、死循环条件 parentIdx < heap.length
     * 4、默认当前minIdx为parentIdx,找到左右子节点
     * 5、先左后右，当子节点小于heap.length 并且小于minVal，那么就把minIdx赋值为该子节点
     * 6、处理过后，判断minIdx和parentIdx。没变说明没交换说明结束了
     * 7、变了说明发生了交换，那么交换parentIdx 和minIdx的值，设置parentIdx=minIdx，进入下一个循环。
     * @param heap
     * @param val
     */
    private static void insertToHeap(int[] heap, int val){
        heap[0] = val;
        int parentIdx = 0;
        while(parentIdx < heap.length){
            int leftChildIdx = parentIdx*2 + 1;
            int rightChildIdx = parentIdx*2 + 2;
            int minIdx = parentIdx;
            int minVal = heap[minIdx];

            if(leftChildIdx < heap.length && heap[leftChildIdx] < minVal){
                minIdx = leftChildIdx;
            }
            if(rightChildIdx < heap.length && heap[rightChildIdx] < minVal){
                minIdx = rightChildIdx;
            }

            if(minIdx == parentIdx){
                return;
            }else{
                int tmpVal = heap[parentIdx];
                heap[parentIdx] = heap[minIdx];
                heap[minIdx] = tmpVal;
                parentIdx = minIdx;
            }
        }

    }
}
